public class SearchTree {
   static class  TreeNode {
       public int val;
       public TreeNode left;
       public TreeNode right;

       public TreeNode(int val) {
           this.val = val;
       }

       public TreeNode root;

        public  TreeNode search(int key){
            TreeNode cur=root;
            while (cur!=null){
                if (cur.val<key){
                    cur=cur.right;
                } else if (cur.val>key) {
                    cur=cur.left;
                }else {
                    return cur;
                }
            }
            return null;
        }
        public  boolean insert(int key){
            TreeNode node =new TreeNode(key);
            if (root==null){
                root=node;
                return true;
            }
            TreeNode cur=root;
            TreeNode p = null;
            while (cur!=null){
                if (cur.val<key){
                    p=cur;
                    cur=cur.right;
                } else if (cur.val>key){
                    p = cur;
                    cur = cur.left;
                }else {
                    return false;
                }
            }
            if (p.val<key){
                p.right=node;
            }else {
                p.left=node;
            }
            return true;
        }
        public void remove(int key){
            TreeNode cur=root;
            TreeNode parent=null;
            while(cur!=null){
                if (cur.val<key){
                    parent=cur;
                    cur=cur.right;
                } else if (cur.val>key) {
                    parent=cur;
                    cur=cur.left;
                }else {
                     removeNode(cur,parent);
                     return;
                }
            }
        }
        private void removeNode(TreeNode cur,TreeNode parent) {
            if (cur.left == null) {
                if (cur == root) {
                    root = root.right;
                } else if (cur == parent.left) {
                    parent.left = cur.right;
                } else {
                    parent.right = cur.right;
                }
            } else if (cur.right == null) {
                if (root == null) {
                    root = root.left;
                } else if (cur == parent.left) {
                    parent.left = cur.left;
                } else {
                    parent.right = cur.left;
                }
            } else {
                TreeNode targetParent = cur;
                TreeNode target = cur.right;
                while (target.left != null) {
                    targetParent = target;
                    target = target.left;
                }
                cur.val = target.val;
                if (targetParent.left == target) {
                    targetParent.left = target.right;
                } else {
                    targetParent.right = target.right;
                }
            }
        }
        }
}
